package com.leetcode.offer.chapter3;

import com.leetcode.basic.ListNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Dennis Li
 * @date 2020/7/13 14:04
 */
public class GetKthFromEnd_22 {

    private Map<Integer, ListNode> map = new HashMap<>();

    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode cur = new ListNode(head.val);
        cur.next = head.next;
        for (int i = 0; i < k; i++)
            cur = cur.next;
        // 注意这道题不能用翻转链表
        // 每次向前移动一位，然后判断下一个结点是不是倒数第k个
        return cur != null ? getKthFromEnd(head.next, k) : head;
    }

    // 一次遍历不能解决问题的时候 -- 考虑用两个指针来遍历
    public ListNode getKthFromEnd2(ListNode head, int k) {
        if(head == null) return null;
        // 快慢指针 -- 保持两个指针的距离
        ListNode fast = head;
        ListNode slow = head;
        // 制造遍历的距离
        while(--k >= 0) {
            if(fast == null) return null;
            fast = fast.next;
        }

        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

}
